package com.solming.leetcode.question;

import java.util.HashMap;

//给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
//
//示例 1 :
//
//输入:nums = [1,1,1], k = 2
//输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
//
public class SubarraySum560 {
    //    自以为题目是在 nums 中有多少 k 长度并且相同数字的数组，计算有多少个这样的数组？
    public static int continuousArray(int[] nums, int k) {
        int len = nums.length;
        if (len == 0 || len < k) {
            return 0;
        }
        int r = 0;
        int compareLen = len - k + 1;
        for (int i = 0; i < compareLen; i++) {
            boolean tmpFlag = true;
            for (int j = 1; j < k; j++) {
                int tmpK = i + j;
                if (tmpK < len && nums[i] != nums[tmpK]) {
                    i++;
                    tmpFlag = false;
                    break;
                }
            }
            if (tmpFlag) {
                r++;
            }


        }
        return r;

    }

    /**
     * 功能描述:解法 1  O（n^2）
     *
     * @Auther: Solming
     * @Date: 2021/8/20
     * @param: [nums, k]
     * @return: int
     **/
    public static int subarraySum(int[] nums, int k) {
        int len = nums.length;
        int count = 0;
        for (int i = 0; i < len; i++) {
            int sum = 0;
            for (int j = i; j < len; j++) {
                sum += nums[j];
                if (k == sum) {
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * 功能描述: 解法二 前缀 + hash（满足条件的存储起来）
     *
     * @Auther: Solming
     * @Date: 2021/8/20
     * @param: [nums, k]
     * @return: int
     **/
    public static int subarraySum2(int[] nums, int k) {
        int len = nums.length;
        int count = 0;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(0, 1);
        int pre = 0;
        for (int i = 0; i < len; i++) {
            pre += nums[i];
            int tmp = pre -k;
            System.out.println();
            if (map.containsKey(tmp)) {
                count += map.get(tmp);
            }
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return count;
    }


    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 1, 1, 2};
//        System.out.println(continuousArray(arr, 2));
        System.out.println(subarraySum2(arr, 2));
    }
}
